# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

import heapq as hq
class Solution:
	# @param {ListNode[]} lists
	# @return {ListNode}
	def mergeKLists(self, lists):
	    # use timsort O(n)
	    nodes = []
	    for head in lists:
	        while head:
	            nodes.append(head)
	            head = head.next

	    if not nodes:
	        return

	    nodes.sort(key=lambda x: x.val)

	    for i in xrange(1, len(nodes)):
	        nodes[i-1].next = nodes[i]

	    nodes[-1].next = None
	    return nodes[0]

if __name__ == '__main__':
	so = Solution()
	num_list = [
		[1,2,4],
		[5,6]

		]
	lists = []
	for nums in num_list:
		H = ListNode(None)
		h = H
		for i in nums:
			h.next = ListNode(i)
			h = h.next
		lists.append(H.next)

	ans = so.mergeKLists(lists)
	count = 0
	while ans:
		count += 1
		print count, ans.val
		ans = ans.next

